package impl.search;

public class InterpolatedOrderedArray<K, V> extends AbstractOrderedArray<K, V> {
    public InterpolatedOrderedArray() {
        super();
    }
    public int search(Object key, int i, int f) {
        int k = key.hashCode();
        if((f-i)>10){
            int ki = (A.get(i).getKey()).hashCode();
            int kf = (A.get(f).getKey()).hashCode();
            double d = ((double)(k - ki)/(double)(kf - ki))*(f - i - 1);
            int id = (int)d;
            if(k<ki){
                return search(key, i, id-1);
            }else if(k>ki){
                return search(key, id+1, f);
            }else{
                return id;
            }
        }else{
            for(int j=i; j<f; j++){
                if(k == A.get(j).getKey().hashCode()){
                    return j;
                }
            }
        }
        return -1;
    }



    public String getType() {
        return "Interpolado";
    }
}